import javax.swing.*;
import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User:DELL
 * Date:2024-12-10
 * Time:23:44
 */
public class Text {
    public ListNode partition(ListNode pHead, int x) {
        if(pHead==null){
            return null;
        }
        //构造两个新链表
        ListNode lessHead=new ListNode(0);
        ListNode tailL=lessHead;
        ListNode greatHead=new ListNode(0);
        ListNode tailG=greatHead;
        //遍历链表，将小于x的往less插，大于的往great插
        ListNode cur=pHead;
        while(cur!=null){
            if(cur.val<x){
                tailL.next=cur;
                tailL=cur;
            }else{
                tailG.next=cur;
                tailG=cur;
            }
            cur=cur.next;
        }
        //将两个表拼接在一起
        tailL.next=greatHead.next;
        tailG.next=null;
        return lessHead.next;
    //合并两个有序数组
        public void merge(int[] nums1, int m, int[] nums2, int n) {
            int end1=m-1;
            int end2=n-1;
            int index=m+n-1;//num1最后一个下标的位置
            //从最后一个入
            while(end1>=0&&end2>=0){
                if(nums1[end1]>nums2[end2]){
                    nums1[index--]=nums1[end1--];
                }else{
                    nums1[index--]=nums2[end2--];
                }
            }
            //nums2可能没有搬完
            while(end2>=0){
                nums1[index--]=nums2[end2--];
            }
    }
        //判断链表是否回文
        public class PalindromeList {
            //1.找到链表的中间节点(快慢指针)
            public ListNode getMiddleNode(ListNode head){
                ListNode fast=head;
                ListNode slow=head;
                //prev保存slow的前一个
                ListNode prev=null;
                while(fast!=null&&fast.next!=null){
                    fast=fast.next.next;
                    prev=slow;
                    slow=slow.next;
                }
                return slow;
            }
            public ListNode reverseList(ListNode head){
                ListNode cur=head;
                ListNode prev=null;
                ListNode next=null;
                while(cur!=null){
                    next=cur.next;
                    cur.next=prev;
                    prev=cur;
                    cur=next;
                }
                return prev;
            }
            public boolean chkPalindrome(ListNode A) {
                //1.找A链表的中间节点
                ListNode mid=getMiddleNode(A);
                ListNode B=mid.next;
                mid.next=null;
                //2.对B结点进行逆置
                B=reverseList(B);
                //2.对A,B链表从前往后进行比较
                ListNode curA=A;
                ListNode curB=B;
                boolean ret=true;
                while(curB!=null){
                    if(curA.val!=curB.val){
                        ret = false;
                        break;
                    }
                    curA=curA.next;
                    curB=curB.next;
                }
                B=reverseList(B);
                mid.next=B;
                return ret;
            }
    public static void main(String[] args) {
        merge();
        partition();
    }
}
